﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <assert.h>
#include <stdbool.h>
// 原题连接：https://leetcode.cn/problems/contains-duplicate/
/*
题目描述：
给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；
如果数组中每个元素互不相同，返回 false 。

示例 1：
输入：nums = [1,2,3,1]
输出：true

示例 2：
输入：nums = [1,2,3,4]
输出：false

示例 3：
输入：nums = [1,1,1,3,3,4,3,2,4,2]
输出：true
*/

// 方法1——暴力法
/*
思路：
对于每一个元素，都向它后边遍历，如果找到一个与它相同的元素
就直接返回true，如果一直找不到，就返回false。
*/

// 有了以上思路，那我们写起代码来也就水到渠成了：
bool containsDuplicate1(int* nums, int numsSize) {
	assert(nums);
	int i = 0;
	int j = 0;
	for (i = 0; i < numsSize - 1; i++) {
		for (j = i + 1; j < numsSize; j++) {
			if (nums[j] == nums[i]) {
				return true;
			}
		}
	}
	return false;
}
// 时间复杂度：O(n^2),n为数组元素个数。
// 空间复杂度：O(1)，我们只需要用到常数级的额外空间。
// 但这个算法复杂度过大，提交给LeetCode这样斯文的网站是不给过的。
// 方法2——排序
/*
当数组在排序之后，相同的元素一定是在相邻位置的，所以我们在排序之后
就可以直接判断相邻元素是否相等，只要发现有一组相邻元素相等就返回true。
一直找不到才返回false。
*/

// 有了以上思路，那我们写起代码来也就水到渠成了：
// 先写一个用于比较两个整型的函数
int cmp_int(const void* p1, const void* p2) {
	assert(p1 && p2);
	return *((int*)p1) - *((int*)p2);
}
bool containsDuplicate2(int* nums, int numsSize) {
	assert(nums);
	// 先进行排序
	qsort(nums, numsSize, sizeof(nums[0]), cmp_int);
	// 再进行遍历
	int i = 0;
	for (i = 0; i < numsSize - 1; i++) {
		if (nums[i] == nums[i + 1]) {
			return true;
		}
	}
	return false;
}